1. Field of the Invention
This invention relates to a method and apparatus for smoothing jagged edges that appear at the interface between different colors in a graphics display.
2. Prior Art
There are two ways to numerically describe a graphics image. The first, typically referred to as vector graphics, represents the image as a combination of points, lines, arcs and other geometric shapes. Each of these components of the image is then successively and cumulatively displayed by an image display device until the complete image is generated.
The second method, typically referred to as raster graphics, represents the image as a rectangular display of minute picture elements ("pixels"). A display screen consists of thousands of tiny dots of color. A pixel may be one dot (as in monochrome monitors), a group of three or four dots (as in color monitors), or a somewhat larger cluster of dots. Here, a pixel will be treated as the smallest region of necessarily uniform color in a graphics image.
Pixels are rectangular (usually square) in shape. As a result, images represented in a pixel-based display are often plagued by a staircase effect apparent in diagonal lines of the image. As a result, some diagonal lines do not appear smooth in the display. FIG. 1(a) shows an image that suffers from the staircase effect. Note, for instance, how the legs in the image have a jagged, rather than smooth, appearance. FIG. 1(b) shows a detailed portion of an image illustrating the staircase effect. As can be seen, the square shape of individual pixels precludes representing diagonal lines of a display in a continuous manner, but, rather, necessitates that these lines be represented as successive discrete jumps from one horizontal (or vertical) level to another. FIG. 1(b) illustrates clearly that the approximate representation of diagonal lines by a pixel-based graphics system results in a "line" that looks like a staircase.
Some previous attempts to solve the "jaggies" problem have employed techniques known as signal processing. These techniques (also known as anti-aliasing), derived from similar techniques employed in audio signal processing, utilize fast Fourier transforms and frequency filtering to eliminate jagged edges. Typically, a three step procedure is used.
In the first step, the set of pixel color representations is transformed into a set of frequency representations. If, for instance, the pixel grid consists of 10,000 pixels, then the 10,000 pixel color representations are transformed into 10,000 frequency representations. However, note that each pixel color representation maps does not map uniquely onto a particular frequency representation. Rather, each frequency representation is a combination of a plurality of pixel color representations.
In the second step, high frequencies are filtered from the set of frequency representations. This is accomplished by assigning a value of zero to frequencies above a certain level. This level is determined empirically as the level which yields the best image quality for "test" images.
In the third step, the set of filtered frequency representations is transformed back into a set of pixel color representations. The color of each pixel is reconstructed from a combination of a plurality of the filtered frequency representations. When the image is redrawn using the new pixel color representations, jagged edges in the image appear to be smoothed.
There are problems with signal processing techniques. First, these techniques are global in effect. That is, they cannot operate only on selected portions of the image (i.e., those portions with jagged edges). As a result, signal processing techniques, while smoothing jagged edges, also smooth the rest of the image as well. Consequently, the anti-aliased image is blurred as compared to the original image.
Second, the input used in these techniques is undesirably limited. The anti-aliased color representation of each pixel may only be affected by nearby pixels (i.e., pixels that are one or two pixels away). Therefore, lines that are either very gently or very steeply sloped may not be adequately smoothed since the signal processing technique may "perceive" them as horizontal or vertical.
Other prior attempts to eliminate jagged edges have involved changing the color of individual pixels in a more localized way, based upon information regarding the content of the image that is known prior to smoothing. The known information is a description of the image as a combination of various mathematical shapes, e.g., squares, rectangles, triangles, circles. Rather than being described on a pixel-by-pixel basis, the image is described by specifying key information for each of the geometric shapes comprising the image. For instance, a circle would be described by giving the location of its center and the magnitude of its radius.
Smoothing of jagged edges in the image is performed in the following way. Using the known mathematical information describing the image, the image is recreated using an expanded temporary pixel grid. For example, the temporary pixel grid might be four times as large as the original pixel grid (i.e., the temporary grid has 4 times as many pixels in both directions of the pixel plane). A correspondence exists between pixels in the original grid and blocks of pixels in the temporary grid. In the case where the temporary grid is four times the size of the original grid, a 4.times.4 array of pixels in the temporary grid corresponds to each pixel of the original grid.
In the original image, pixels near an edge will take on one of the two edge colors. When the image is redrawn on the expanded temporary pixel grid, each pixel in the original grid will correspond to a 4.times.4 array of pixels in the temporary grid. Some of the pixels in that "edge pixel array" will take on one of the edge colors and some will take on the other edge color. The important point to note is that for each 4.times.4 pixel array representing an edge pixel in the original image, not all of the pixels of the array will be of one color.
After the image is converted to the expanded temporary pixel grid, for those pixel arrays representing edge pixels in the original pixel grid, a ratio is calculated representing the fraction of pixels of one color out of the total number of pixels in the array. So, for example, in an edge pixel array with black and white as the edge colors, the fraction of either black or white pixels will be N/16 where 0&lt;N&lt;16. This information representing the fractional color composition of the 4.times.4 edge pixel arrays in the expanded pixel grid is then used to modify the original pixel grid. Using the previous example, with black and white as edge colors, a particular edge pixel in the original grid is changed to be some shade of gray, rather than being either black or white as in the original image. For instance, an edge pixel in the original grid corresponding to a 4.times.4 array in the temporary grid that contains 13 black pixels and 3 white pixels, would be changed to a relatively dark shade of gray in the smoothed image. In this way, the color of edge pixels in the original image is adjusted to smooth the transitions between colors at feature edges.
While this approach has an advantage over the signal processing approach in that it smoothes only selected portions of the image, rather than the entire image, thus avoiding blurring of the image, there are problems with such techniques. First, the approach is limited in application. It may only be used when the features in a particular image are known prior to application of the smoothing method, and these features may be described as combinations of simple geometric shapes. Thus, this method is not useful in smoothing jagged edges in complex images.
Second, this approach requires "pre-processing" of the image to provide a more synthesized representation than that afforded by a rudimentary pixel-map representation of the image. This type of approach will not work if only a simple pixel-map representation of the pixel grid exists, i.e., if only the characteristics of each pixel are known and no information regarding the relationship of one pixel to another is known. This is because, when pixels in the original grid are mapped onto a 4.times.4 pixel array in the expanded pixel grid, the pixel representation is not refined in any way. In other words, all of the pixels in each 4.times.4 array will be the same color as the corresponding pixel in the original grid. When the expanded pixel grid is mapped back on to the original grid, the color of each pixel in the original grid remains the same.
This does not occur in the prior method described, because transferring the original grid on to an expanded grid refines the pixel representation near edges. Some of the pixels in each 4.times.4 edge pixel array will be one color, some another. Thus, when the image is retransferred to the original grid, the color of edge pixels changes from the original color. The additional information known about the image (i.e., composition of the image as a sum of various mathematical shapes) is used to refine the image representation in an expanded grid, and this refinement is, in turn, used to smooth edges when the image is redisplayed using the original pixel grid.